class Node:
    def __init__(self, val, prev=None, next=None, child=None):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child

class Solution:
    def flatten(self, head):
        if head is None:
            return None
        
        cur = head
        while cur is not None:
            if cur.child is None:
                cur = cur.next
                continue
            
            res = self.flatten(cur.child)
            cnext = cur.next
            if cnext is None:
                cur.next = res
                res.prev = cur
            else:
                cur.next = res
                res.prev = cur
                temp = res
                while temp.next is not None:
                    temp = temp.next
                temp.next = cnext
                cnext.prev = temp
            cur = cnext
        return head

def display(head):
    while head is not None:
        print(head.val, end=' ')
        head = head.next
    print("\n")

def reversedisplay(head):
    cur = head
    while cur.next is not None:
        cur = cur.next
    
    while cur is not None:
        print(cur.val, end=" ")
        cur = cur.prev

if __name__ == '__main__':
    """
     1---2---3---4---5---6--NULL
         |
         7---8---9---10--NULL
             |
             11--12--NULL
"""
    node1 = Node(1)
    node2 = Node(2)
    node3 = Node(3)
    node4 = Node(4)
    node5 = Node(5)
    node6 = Node(6)
    node7 = Node(7)
    node8 = Node(8)
    node9 = Node(9)
    node10 = Node(10)
    node11 = Node(11)
    node12 = Node(12)

    node1.next = node2

    node2.prev = node1
    node2.next = node3

    node3.prev = node2
    node3.next = node4

    node4.prev = node3
    node4.next = node5

    node5.prev = node4
    node5.next = node6

    node6.prev = node5

    node3.child = node7

    node7.next = node8

    node8.prev = node7
    node8.next = node9

    node9.prev = node8
    node9.next = node10

    node10.prev = node9

    node8.child = node11

    node11.next = node12
    node12.prev = node11

    s = Solution()
    head = s.flatten(node1)
    display(head)
    reversedisplay(head)

